import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.SortedSet;
import java.util.TreeSet;

class Star implements Comparable<Star> {

	static int PRIME = 2053;
	int x, y, z;

	
	public Star(int x, int y, int z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}

	@Override
	public int compareTo(Star o) {
		int v;
		v = x - o.x;
		if (v != 0)
			return v;
		v = y - o.y;
		if (v != 0)
			return v;
		v = z - o.z;
		if (v != 0)
			return v;
		return 0;
	}

	@Override
	public int hashCode() {
		Star rndStar = new Star(10, 100, 1000);
		return (int) ((Math.ceil(this.x/100d)*100d*rndStar.x + Math.ceil(this.y/100d)*100d*rndStar.y + Math.ceil(this.z/100d)*100d*rndStar.z) % PRIME);
	}

	public boolean isInRange(Star star, int radius) {
		int distanceX = Math.abs(this.x - star.x);
		int distanceY = Math.abs(this.y - star.y);
		int distanceZ = Math.abs(this.z - star.z);
		int maxDistance = Math.max(distanceX, Math.max(distanceY, distanceZ));
		if(maxDistance < radius)
			return true;
		return false;
	}
}

public class StarMap {

	static String FILENAME = "/Users/Dennis/Documents/workspace/DSEA Übung/Blatt 8_2/stars.txt";
	static int NUM_STARS = 1000;
	static int ALPHA = 1;
	static int TABLESIZE = NUM_STARS * ALPHA;
	static int BOXSIZE = 100;
	
	// a collection containing all stars
	Collection<Star> stars = new ArrayList<Star>(NUM_STARS);
	Star centerStar;
	int radius;
	public static Hashtable<Integer, ArrayList<Star>> memorizedData = new Hashtable<Integer, ArrayList<Star>>();
	
	public static void main(String[] args) throws FileNotFoundException {

		// load stars and create hashtable
		StarMap starMap = new StarMap();
		starMap.loadStars();
		//System.out.println("# Stars: " + starMap.stars.size());
		//System.out.println("# Star: " + starMap.centerStar.x + ", "+ starMap.centerStar.y + ", " + starMap.centerStar.z);
		//System.out.println("# Radius: " + starMap.radius);
		starMap.calcHashTable();
		
		
/*		//Zaehlt nativ alle Sterne in Range
		int count = -1;
		for(Star star: starMap.stars)
			if(star.isInRange(starMap.centerStar, starMap.radius))
				count++;
		System.out.println("# Stars in Range: "+count);*/
		
		
		// get nearest Stars
		Collection<Star> nearestStars = starMap.getNearest(starMap.centerStar,starMap.radius);

		// print nearest Stars
		if(nearestStars != null) {
			SortedSet<Star> nearestStarsSorted = new TreeSet<Star>(nearestStars);
			System.out.println("nearest stars: " + nearestStarsSorted.size());
			for (Star star : nearestStarsSorted)
				System.out.format("%d %d %d\n", star.x, star.y, star.z);
		}
	}

	private void loadStars() throws FileNotFoundException {
		Scanner s = new Scanner(new File(FILENAME));
		for (int i = 0; i < NUM_STARS; ++i) {
			int x = s.nextInt();
			int y = s.nextInt();
			int z = s.nextInt();
			stars.add(new Star(x, y, z));
		}
		int x = s.nextInt();
		int y = s.nextInt();
		int z = s.nextInt();
		centerStar = new Star(x, y, z);
		radius = s.nextInt();
		s.close();
	}

	private void calcHashTable() {
		for (Star star : stars) {
			ArrayList<Star> sameHashKeyStars = StarMap.memorizedData.get(star.hashCode());
			if (sameHashKeyStars == null) 
			{
				sameHashKeyStars = new ArrayList<Star>();
				sameHashKeyStars.add(star);
			}
			else
				sameHashKeyStars.add(star);
			
			StarMap.memorizedData.put(star.hashCode(), sameHashKeyStars);
			//System.out.println(star.hashCode());
		}		
	}

	private Collection<Star> getNearest(Star star, int radius) {
		Collection<Star> nearestStars = new ArrayList<Star>();
		//fuer jede Box in Range werden die beinhaltenden Sterne gecheckt und in der ArrayList gespeichert
		for(Integer hashcode: getAllBoxes(star,radius))
					nearestStars.addAll(getNearestInBox(hashcode, star, radius));
		return nearestStars;
	}
	
	// Gibt alle Boxen innerhalb des Radius zurueck
	// TODO Hier werden 64/64 Boxen erkannt. Aber insgesamt nur 11 Sterne in Range.
	private LinkedList<Integer> getAllBoxes(Star star, int radius){
		LinkedList<Integer> boxID = new LinkedList<Integer>();
		//for(int rad = radius; rad >= 0; rad -= BOXSIZE)
			for(double i = -1; i <= 1; i += 0.5)
				for(double j = -1; j<= 1; j += 0.5)
					for(double k = -1; k <= 1; k += 0.5){
						Star nextBox = new Star(star.x + (int)(i*radius),star.y + (int)(j*radius),star.z + (int)(k*radius));
						if(boxID.contains(nextBox.hashCode()))
							continue;
						boxID.add(nextBox.hashCode());
					}
						
		System.out.println("# Boxes in Range: "+boxID.size());
		return boxID;
	}
	
	//checkt die box auf punkte in range
	private Collection<Star> getNearestInBox(int key, Star star, int radius) {
		ArrayList<Star> stararray = StarMap.memorizedData.get(key);
		ArrayList<Star> starsInRange = new ArrayList<Star>();
		if(stararray != null)
			for(Star stern: stararray)
				if(stern.isInRange(star, radius))
					starsInRange.add(stern);
		return starsInRange;
	}
}